package com.leetcode.array;

import java.util.SortedSet;
import java.util.TreeSet;

/**
 * @author: ZhouBert
 * @date: 2019/10/1
 * @description: 220. 存在重复元素 III
 * B
 * 给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的【绝对值】最大为 t，并且 i 和 j 之间的差的绝对值最大为 k。
 * <p>
 * 示例 1:
 * 输入: nums = [1,2,3,1], k = 3, t = 0
 * 输出: true
 * 示例 2:
 * 输入: nums = [1,0,1,1], k = 1, t = 2
 * 输出: true
 * 示例 3:
 * 输入: nums = [1,5,9,1,5,9], k = 2, t = 3
 * 输出: false
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/contains-duplicate-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ContainsNearbyAlmostDuplicateIII220 {

	/**
	 * I:使用双指针（相隔k）：遍历一遍去判断 t or -t
	 * O(n)	--XX 貌似我的理解错了！
	 * https://blog.csdn.net/qq_35170267/article/details/81200659
	 * @param nums
	 * @param k
	 * @param t
	 * @return
	 */
	public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
		if (k < 1 || t < 0)
			return false;
		SortedSet<Long> binTree = new TreeSet<>();
		for (int i = 0; i < nums.length; i++) {
			SortedSet<Long> son = binTree.subSet((long) nums[i] - t, (long) nums[i] + t + 1);
			if (!son.isEmpty())
				return true;
			if (i >= k)
				binTree.remove((long) nums[i - k]);
			binTree.add((long) nums[i]);
		}
		return false;
	}

	public static void main(String[] args) {
		int[] nums = new int[]{1, 2, 3, 1};
		int k = 3;
		int t = 0;

		nums = new int[]{1, 0, 1, 1};
		k = 1;
		t = 2;
		System.out.println(containsNearbyAlmostDuplicate(nums, k, t));
	}
}
